携Science封面、NIPS最佳论文，CMU大神Noam博士毕业，论文已公开

数学算法俱乐部

日期：2020年10月05日

正文共：2046字16图

预计阅读时间：6分钟

来源：机器之心

还记得在双人无限扑克和多人无限扑克中战胜人类顶级玩家的游戏 AI 系统冷扑大师（Libratus）和 Pluribus 吗？近日，这两个 AI 系统的开发者之一、CMU 大神宣布其完成博士论文，并即将从 CMU 毕业。

当地时间 9 月 21 日，FAIR 研究科学家 Noam Brown 在推特宣布其顺利完成了 CMU 博士论文答辩，并公开了长达 230 页的超硬核博士论文《Equilibrium Finding for Large Adversarial Imperfect-Information Games》以及 101 页的 slides。

Noam 在论文前言中表示，除了章节 5.3 中描述的 ReBel 算法，论文中所有其他研究都是与其导师 Tuomas Sandholm 合作完成的。在整个研究过程中，Tuomas 给了 Noam 耐心指导。Noam 表示，如果没有导师的悉心指导，他肯定不会顺利地完成博士学位。

Noam Brown 与其导师 Tuomas Sandholm 教授（左）。

Noam Brown 的博士论文题目为《大型对抗性不完美信息博弈的均衡发现》。不完美信息博弈模拟了多个智能体与私人信息之间的交互。在这一设置下，一个典型的目标是近似一个均衡，其中所有智能体的策略都能达到最优。

完美信息博弈（Perfect-information Games）和不完美信息博弈（Imperfect-information Games）是游戏中信息博弈的两种主要形式。在游戏中，完美信息博弈的前提是所有玩家都知道关于游戏的信息，如规则等；而不完美信息博弈中的玩家对正在玩的游戏没有共同知识，如其他玩家是谁、哪些策略或行动是可行的、结果如何取决于行动等。就难度而言，信息的不完美增加了玩家决策选择的难度，因而博弈分析的难度也更大。

围棋、国际象棋、跳棋等棋类游戏属于完美信息博弈。扑克牌则属于典型的不完美信息博弈，这也是 Noam Brown 一直以来的研究重心。从 2017 年的 AI 系统 Libratus 到 2019 年的新算法 Pluribus，它们都属于不完美信息博弈的范畴。

在论文中，Noam Brown 对博士期间的一系列研究成果进行了汇总。机器之心对该论文的核心内容进行了简要介绍，感兴趣的读者可以阅读原论文。

• 论文地址：http://www.cs.cmu.edu/~noamb/thesis.pdf

• Slides 地址：http://www.cs.cmu.edu/~noamb/thesis_slides.pdf

博士论文简介

这篇博士论文详述了大型对抗性不完美信息博弈中均衡计算的一系列进展。这些新技术使得 AI 智能体首次有可能在无限注扑克游戏中击败顶级职业玩家，而这正是几十年来 AI 和博弈论领域一直存在的重大挑战性难题。

反事实遗憾最小化（CFR）的改进

作者首先介绍了对反事实遗憾最小化（counterfactual regret minimization, CFR）做出的改进，这是一种在双人零和博弈中收敛至纳什均衡的迭代算法。此外还描述了 CFR 的新变体，它们利用折扣原则（discounting）来显著加快收敛速度。

CFR 方法。

然后，作者介绍了理论上合理的剪枝（pruning）技术，这些技术可以在大型博弈中呈数量级地加快收敛速度。

CFR 中的剪枝流程。

将 CFR 扩展至大型博弈

作者描述了通过自动抽象和函数近似算法将 CFR 扩展至大型博弈的新方法。

具体而言，作者介绍了首个在不完美信息博弈中离散化连续动作空间的算法，该算法被证明局部最优。但是，这种算法需要大量的领域知识，并且难以扩展至其他博弈中。

以往方法的局限性。

所以，作者提出了 CFR 的一种变体 Deep CFR，它使用了神经网络函数近似，而没有使用基于 bucketing 的抽象。Deep CFR 是首个可以扩展至大型博弈的 non-tabular 形式的 CFR，并且使得 CFR 在几乎没有领域知识的设置下实现部署。

利用 Deep CFR 扩展至大型博弈中。

不断改进的搜索技术

作者提出了一种新的不完美信息博弈搜索技术，该技术确保智能体的搜索策略不被对手利用。这些新的搜索形式在理论和实践两方面均优于以往方法。

此外，作者介绍了一种深度受限（depth-limited）搜索方法，它的计算成本显著低于以往方法。

Pluribus 算法中的深度受限搜索。

最后，作者提出了一种新型 ReBel 算法，它在训练和测试时结合强化学习和搜索，并为缩小完美信息博弈和不完美信息博弈研究的差距迈出了关键一步。

在双人无限注德州扑克中的结果对比。

以下是博士论文的章节目录：

致力于德扑游戏 AI 研究的 CMU 大神 Noam Brown

Noam Brown，Facebook 人工智能实验室的研究科学家，他致力于结合计算博弈论和机器学习来开发能够在不完美信息多智能体环境中进行策略推理的 AI 系统，其研究成果应用到了首个分别在在双人无限扑克和多人无限扑克中战胜人类顶级玩家的 Libratus 和 Pluribus。这两个游戏 AI 系统为 Noam Brown 带来了巨大的荣誉。

2017 年，Noam Brown 与其导师 Tuomas Sandholm 开发的 AI 系统 Libratus 在宾夕法尼亚州匹兹堡 Rivers 赌场持续 20 天 1 对 1 无限制德扑比赛中成功战胜了 4 名全球顶级职业玩家。该研究登上了《科学》杂志，与研究相关的另一篇论文《Safe and Nested Subgame Solving for Imperfect-Information Games》也获得了 NIPS 2017 最佳论文奖。

此外，Noam 团队还因此获得了 IJCAI 颁发的第二枚马文 · 明斯基奖章（Marvin Minsky Medal）。

Noam 在 IJCAI 2019 大会上领取马文 · 明斯基奖章证书。

2019 年，Noam Brown 与其导师 Tuomas Sandholm 在 Libratus 的基础上，开发出了所需算力更少的新算法 Pluribus。在为期 12 天、超过 10000 手牌的比赛中，Pluribus 击败了 15 名人类顶级玩家。

这是 AI 首次在玩家人数（或队伍）大于 2 的大型基准游戏中击败顶级职业玩家。Pluribus 不仅登上了《科学》杂志的封面，还被该杂志列为 2019 年度十大突破科研成就之一。

Pluribus 登上了《科学杂志》封面。

此外，Noam 还曾获得 2017 年度 Allen Newell「卓越研究奖」，也曾被 MIT 科技评论评选为 2019 年度「35 岁以下科技精英」（MIT TR35）。2019 年，Noam Brown 与其导师 Tuomas Sandholm 合著的论文《Solving Imperfect-Information Games via Discounted Regret Minimization》获得了 AAAI 杰出论文荣誉提名奖。

参考链接：

https://mp.weixin.qq.com/s/IoaSWYvBn_M2Io5EGcDWOA

https://www.cs.cmu.edu/~noamb/

— THE END —

☞21页优雅读博指南：佐治亚理工学院助理教授Eric Gilbert撰写，入坑前必读
☞谱聚类（spectral clustering）原理总结☞如何用数学方法估算一个女生前男友的数量？☞机器学习中需要了解的 5 种采样方法☞北大读博手记：怎样完成自己的博士生涯？非常具有指导性！☞每个程序员都必须知道的8种数据结构